The subject matter discussed in the background section should not be assumed to be prior art merely as a result of its mention in the background section. Similarly, a problem mentioned in the background section or associated with the subject matter of the background section should not be assumed to have been previously recognized in the prior art. The subject matter in the background section merely represents different approaches, which in and of themselves may also be inventions.
Given a large collection (millions or billions) of small sets of items (which may be called market baskets) sampled from an existing universe of items (such as products, services, or search terms), automated recommendation of items is often based on the identification of frequently occurring item sets, which are sets of items that were purchased or otherwise chosen together. There are other recommendation algorithms, such collaborative filtering, for circumstances when system users sample one item at a time. Frequent item sets is for circumstances when system users choose items together. Market basket analysis is a process in which retailers evaluate information in such market baskets to understand the purchase behavior of customers. This information can then be analyzed for purposes of cross-selling, the practice of selling an additional product or service to an existing customer. Examples of market basket analysis for cross selling are automated recommendations such as “customers who bought book A also bought book B,” and “People who read ‘History of Portugal’ were also interested in ‘Naval History.’” Many database systems use the Apriori algorithm to evaluate frequent item sets for market basket analysis. The Apriori algorithm identifies the individual items that appear the most frequently in a database's item sets, and then extends these frequent individual items to larger and larger item sets, provided that the larger item sets appear sufficiently often in the database's item sets.
Depending on the nature and size of the item sets, a frequent pattern (FP) tree algorithm can execute much faster than the Apriori algorithm executes. The frequent pattern tree algorithm places item sets in a tree, recursively building the tree based on the count for each of the items in the item sets. For each item set, the frequent pattern tree algorithm sorts its items, left to right, in descending order. The frequent pattern tree algorithm identifies the leftmost item with the most item sets, removes this item from the item sets, and represents this item as a root node with the count of all its item sets. Then the frequent pattern tree algorithm recursively looks at the next position in the descending order of items, and finds the most represented remaining item, and represents that item as a child node. The frequent pattern tree algorithm repeats this process, representing more items as child nodes until the frequent pattern tree algorithm is done with the descending order of items, thereby creating a tree in which each original item set is a path in the tree. Then the frequent pattern tree algorithm generates all of the possible item sets by proceeding upward from the leaves in the tree. If the item sets include enough repetition of items, the frequent pattern tree algorithm can execute in memory.
A search box can be a graphical control element used in computer programs, such as file managers, or web browsers, and on web sites. A search box may be a single-line text box with the dedicated function of accepting user input that is used as a query to search a database. Search boxes on web pages can be used to allow users to enter a query to be submitted to a Web search engine server-side script, where an index database is searched for entries that contain one or more of the user's search terms, which may be called query items. Search boxes can be accompanied by a search button, which may be indicated by a magnifying glass symbol, to submit a query for a search. However, the search button can be omitted as the user may press the enter key to submit a query for a search, or the query can be sent automatically to present the user with real-time results. Depending on the particular implementation, a search box may be accompanied by a drop-down list to present the users with past queries or suggested queries. Search boxes can have other features to help the user, such as autocomplete, a spelling checker, etc. Search boxes may also be accompanied by drop-down menus or other input controls to allow the user to restrict the search or choose for which type of content to search. A suggested query drop-down list can show a user shortcuts while a query is entered into a search box. Before the query is completely entered, a drop-down list with the suggested completions may appear to provide options to select. The suggested queries can enable the searcher to complete the required search quickly. As a form of auto completion, the suggested query list is distinct from a search history in that the suggested query list attempts to be predictive even when the user is entering a query for the initial time. Data that supports suggested queries may come from popular searches, sponsors, geographic location, or other sources. These suggested query lists can be used by operating systems, web browsers, and various websites, particularly search engines.
Autocomplete may be a feature in which an application predicts the rest of a word or a query that a user is typing. In graphical user interfaces, users can press the tab key to accept a suggested completion or the down arrow key to accept one of several suggested completions. Autocomplete speeds up human-computer interactions when it correctly predicts the word or query that a user intends to enter after only a few characters have been entered into an input field.